//package compile.lesson4;
//
//import java.util.*;
//
//public class LR0Parser {
//
//    // 定义文法规则
//    ArrayList<String> grammar = new ArrayList<>(Arrays.asList(
//            "S->E", "E->xxT", "T->y"
//    ));
//
//    // 定义文法符号集合
//    HashSet<String> symbols = new HashSet<>();
//
//    // 定义项目集规范族
//    ArrayList<HashSet<String>> canonicalCollection = new ArrayList<>();
//
//    // 定义LR(0)分析表
//    String[][] actionTable;
//    int[][] gotoTable;
//
//    // 在LR(0)分析表中指定位置插入操作
//    private void insertAction(int state, String lookahead, String action) {
//        int tokenIdx = new ArrayList<>(symbols).indexOf(lookahead);
//        actionTable[state][tokenIdx] = action;
//    }
//
//    // 在LR(0)分析表中指定位置插入状态
//    private void insertGoto(int state, String lookahead, int nextState) {
//        int tokenIdx = new ArrayList<>(symbols).indexOf(lookahead);
//        gotoTable[state][tokenIdx] = nextState;
//    }
//
//    // 从文法规则中提取文法符号集合
//
//    /**
//     * 执行完成后：symbol中是【S,T,E,x,y】
//     */
//    private void extractSymbols() {
//        for (String rule : grammar) {
//            String[] parts = rule.split("->");
//            symbols.add(parts[0]);
//            for (String s : parts[1].split("")) {
//                symbols.add(s);
//            }
//        }
//    }
//
//    // 获取初始项目集{S' -> .S}
//    private HashSet<String> getInitialState() {
//        HashSet<String> state = new HashSet<>();
//        state.add("S'->.S");
//        closure(state);
//        return state;
//    }
//
//    // 获取规范项目集族
//    private void getCanonicalCollection() {
//
//        // 初始化第一个状态
//        HashSet<String> initialState = getInitialState();
//        canonicalCollection.add(initialState);
//
//        // 用队列存储项目集集合
//        Queue<HashSet<String>> queue = new LinkedList<>();
//        queue.offer(initialState);
//
//        while (!queue.isEmpty()) {
//            HashSet<String> state = queue.poll();
//
//            for (String symbol : symbols) {
//                System.out.println("getCanonicalCollection");
//                HashSet<String> gotoState = goTo(state, symbol);
//                if (gotoState.isEmpty()) {
//                    continue;
//                }
//                if (!canonicalCollection.contains(gotoState)) {
//                    canonicalCollection.add(gotoState);
//                    queue.offer(gotoState);
//                }
//            }
//        }
//    }
//
//
//
//    // 计算项目集闭包
//    private void closure(HashSet<String> I) {
//        boolean changed = true;
//        while (changed) {
//            changed = false;
//            ArrayList<String> items = new ArrayList<>(I);
//            for (int k = 0; k < items.size(); k++) {
//                String[] parts = items.get(k).split("->");
//                String right = parts[1];
//                int dotIndex = right.indexOf(".");
//                if (dotIndex < right.length() - 1) {
//                    String B = String.valueOf(right.charAt(dotIndex + 1));
//                    if (!symbols.contains(B)) {
//                        continue;
//                    }
//                    // 计算B的产生式
//                    for (String rule : grammar) {
//                        if (rule.startsWith(B + "->")) {
//                            String newItem = B + "->." + rule.substring(3);
//                            if (!I.contains(newItem)) {
//                                I.add(newItem);
//                                changed = true;
//                            }
//                        }
//                    }
//                }
//            }
//        }
//    }
//
//    // 计算状态集合的转移状态集合
//    private HashSet<String> goTo(HashSet<String> I, String X) {
//        HashSet<String> J = new HashSet<>();
//        for (String item : I) {
//            String[] parts = item.split("->");
//            String right = parts[1];
//            int dotIndex = right.indexOf(".");
//            if (dotIndex < right.length() - 1 && String.valueOf(right.charAt(dotIndex + 1)).equals(X)) {
//                String newItem = parts[0] + "->" + right.substring(0, dotIndex + 1) + X + "." + right.substring(dotIndex + 2);
//                J.add(newItem);
//            }
//        }
//        closure(J);
//        return J;
//    }
//
//    // 构建LR(0)分析表
//    private void buildTables() {
//        actionTable = new String[canonicalCollection.size()][symbols.size()];
//        gotoTable = new int[canonicalCollection.size()][symbols.size()];
//
//        // 初始化
//        for (int i = 0; i < canonicalCollection.size(); i++) {
//            Arrays.fill(actionTable[i], "");
//            Arrays.fill(gotoTable[i], -1);
//        }
//
//        // 填充动作
//        for (int i = 0; i < canonicalCollection.size(); i++) {
//            HashSet<String> I = canonicalCollection.get(i);
//            for (String item : I) {
//                String[] parts = item.split("->");
//                String right = parts[1];
//                int dotIndex = right.indexOf(".");
//                if (dotIndex == right.length() - 1) {
//                    // 移入
//                    if (parts[0].equals("S'")) {
//                        insertAction(i, "$", "acc");
//                    } else {
//                        for (String token : follow(parts[0])) {
//                            insertAction(i, token, "reduce " + parts[0] + "->" + right.substring(0, dotIndex));
//                        }
//                    }
//                } else {
//                    String a = String.valueOf(right.charAt(dotIndex + 1));
//                    if (symbols.contains(a)) {
//                        HashSet<String> J = goTo(I, a);
//                        int jIndex = canonicalCollection.indexOf(J);
//                        insertAction(i, a, "shift " + jIndex);
//                    }
//                }
//            }
//        }
//
//        // 填充转移
//        for (int i = 0; i < canonicalCollection.size(); i++) {
//            for (String symbol : symbols) {
//                if (symbols.contains(symbol)) {
//                    HashSet<String> J = goTo(canonicalCollection.get(i), symbol);
//                    int jIndex = canonicalCollection.indexOf(J);
//                    if (jIndex != -1) {
//                        insertGoto(i, symbol, jIndex);
//                    }
//                }
//            }
//        }
//    }
//
//    // 计算非终结符的FOLLOW集合
//    private HashSet<String> follow(String variable) {
//        HashSet<String> result = new HashSet<>();
//        if (variable.equals("S'")) {
//            result.add("$");
//        }
//        for (String rule : grammar) {
//            String[] parts = rule.split("->");
//            String right = parts[1];
//            int idx = right.indexOf(variable);
//            if (idx != -1 && idx < right.length() - 1) {
//                String nextSymbol = String.valueOf(right.charAt(idx + 1));
//                if (symbols.contains(nextSymbol)) {
//                    result.addAll(first(nextSymbol));
//                } else if (!nextSymbol.equals(variable)) {
//                    result.add(nextSymbol);
//                } else {
//                    result.addAll(follow(parts[0]));
//                }
//            } else if (idx == right.length() - 1) {
//                result.addAll(follow(parts[0]));
//            }
//        }
//        return result;
//    }
//
//    // 计算符号串的FIRST集合
//    private HashSet<String> first(String str) {
//        HashSet<String> result = new HashSet<>();
//        String[] symbols = str.split("");
//        int i = 0;
//        while (i < symbols.length) {
//            String symbol = symbols[i];
//            if (!this.symbols.contains(symbol)) {
//                result.add(symbol);
//                break;
//            }
//            HashSet<String> fi = new HashSet<>(grammar.size());
//            for (String rule : grammar) {
//                String[] parts = rule.split("->");
//                if (parts[0].equals(symbol)) {
//                    HashSet<String> newFi = first(parts[1]);
//                    fi.addAll(newFi);
//                }
//            }
//            if (fi.contains("ε")) {
//                fi.remove("ε");
//                result.addAll(fi);
//                i++;
//            } else {
//                result.addAll(fi);
//                break;
//            }
//        }
//        if (i == symbols.length) {
//            result.add("ε");
//        }
//        return result;
//    }
//
//    // 测试输入字符串是否被文法接受
//    public boolean parse(String input) {
//        Stack<Integer> stateStack = new Stack<>();
//        Stack<String> symbolStack = new Stack<>();
//        stateStack.push(0);
//
//        for (String token : input.split("")) {
//            int state = stateStack.peek();
//            int tokenIdx = new ArrayList<>(symbols).indexOf(token);
//            String action = actionTable[state][tokenIdx];
//
//            if (action.startsWith("shift ")) {
//                // 移入操作
//                int nextState = Integer.parseInt(action.split(" ")[1]);
//                stateStack.push(nextState);
//                symbolStack.push(token);
//            } else if (action.startsWith("reduce ")) {
//                // 规约操作
//                String production = action.split(" ")[1];
//                String[] parts = production.split("->");
//
//                for (int i = 0; i < parts[1].length(); i++) {
//                    stateStack.pop();
//                    symbolStack.pop();
//                }
//
//                int newState = gotoTable[stateStack.peek()][new ArrayList<>(symbols).indexOf(parts[0])];
//                stateStack.push(newState);
//                symbolStack.push(parts[0]);
//            } else if (action.equals("acc")) {
//                // 接受操作
//                return true;
//            } else {
//                // 错误操作
//                return false;
//            }
//        }
//
//        return false;
//    }
//
//    public static void main(String[] args) {
//        LR0Parser parser = new LR0Parser();
//        parser.extractSymbols();
//        parser.getCanonicalCollection();
//        parser.buildTables();
//
//        // 打印LR(0)分析表
//        System.out.printf("%10s |", "");
//        for (String symbol : parser.symbols) {
//            System.out.printf("%10s |", symbol);
//        }
//        System.out.println();
//        for (int i = 0; i < parser.canonicalCollection.size(); i++) {
//            System.out.printf("%10d |", i);
//            for (int j = 0; j < parser.symbols.size(); j++) {
//                System.out.printf("%10s |", parser.actionTable[i][j]);
//            }
//            System.out.println();
//        }
//
//        // 测试输入字符串是否被文法接受
//        System.out.println(parser.parse("i+i*i"));
//    }
//
////    public static void main(String[] args) {
////        LR0Parser parser = new LR0Parser();
////        parser.extractSymbols();
////        parser.getCanonicalCollection();
////        parser.buildTables();
////
////        for (int i = 0; i < parser.canonicalCollection.size(); i++) {
////            System.out.println("State " + i + ":");
////            HashSet<String> state = parser.canonicalCollection.get(i);
////            for (String item : state) {
////                System.out.println("\t" + item);
////            }
////            System.out.println();
////        }
////    }
//
//}